package org.flint.data.structure.uf.impl;

import com.google.common.base.Preconditions;
import org.flint.data.structure.uf.UnionFind;

/**
 * @author flint92
 */
public class QuickFind implements UnionFind {

    private int[] ids;

    public QuickFind(int size) {
        ids = new int[size];

        for (int i = 0; i < size; i++) {
            ids[i] = i;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);

        if (pId == qId) {
            return;
        }

        for (int i = 0, len = getSize(); i < len; i++) {
            if (ids[i] == pId) {
                ids[i] = qId;
            }
        }
    }

    @Override
    public int getSize() {
        return ids.length;
    }

    /**
     * 查找元素对应的集合编号
     *
     * @param p 元素p
     * @return 集合编号
     */
    private int find(int p) {
        Preconditions.checkElementIndex(p, getSize());
        return ids[p];
    }
}
